翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Mu-recursive function ： ウィキペディア英語版 Μ-recursive function In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers that are "computable" in an intuitive sense. In fact, in computability theory it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines. The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every μ-recursive function is a primitive recursive function—the most famous example is the Ackermann function. Other equivalent classes of functions are the λ-recursive functions and the functions that can be computed by Markov algorithms. The set of all recursive functions is known as R in computational complexity theory. ==Definition== The μ-recursive functions (or partial μ-recursive functions) are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the μ operator. The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) is the class of primitive recursive functions. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial recursive functions. For example, the Ackermann function can be proven to be total recursive, but not primitive. Initial or "basic" functions: (In the following the subscripting is per Kleene (1952) p. 219. For more about some of the various symbolisms found in the literature see Symbolism below.) #Constant function: For each natural number $n\backslash ,$ and every $k\backslash ,$: #:$f(x\_1,\backslash ldots,x\_k)\; =\; n\backslash ,$. #:Alternative definitions use compositions of the successor function and use a zero function, that always returns zero, in place of the constant function. # Successor function S: #: $S(x)\; \backslash stackrel\; f(x)\; =\; x\; +\; 1\backslash ,$ # Projection function $P\_i^k$ (also called the Identity function $I\_i^k$): For all natural numbers $i,\; k\backslash ,$ such that $1\; \backslash le\; i\; \backslash le\; k$: #: $P\_i^k\; \backslash stackrel\; f(x\_1,\backslash ldots,x\_k)\; =\; x\_i$. Operators: # Composition operator $\backslash circ\backslash ,$ (also called the substitution operator): Given an m-ary function $h(x\_1,\backslash ldots,x\_m)\backslash ,$ and m k-ary functions $g\_1(x\_1,\backslash ldots,x\_k),\backslash ldots,g\_m(x\_1,\backslash ldots,\; x\_k)$: #:$h\; \backslash circ\; (g\_1,\; \backslash ldots,\; g\_m)\; \backslash stackrel\; f(x\_1,\backslash ldots,x\_k)\; =\; h(g\_1(x\_1,\backslash ldots,x\_k),\backslash ldots,g\_m(x\_1,\backslash ldots,x\_k))\backslash ,$. # Primitive recursion operator $\backslash rho\backslash ,$: Given the k-ary function $g(x\_1,\backslash ldots,x\_k)\backslash ,$ and k+2 -ary function $h(y,z,x\_1,\backslash ldots,x\_k)\backslash ,$: #: $\backslash begin$ \rho(g, h) &\stackrel f(y, x_1,\ldots, x_k) \quad \\ f(0,x_1,\ldots,x_k) &= g(x_1,\ldots,x_k) \\ f(y+1,x_1,\ldots,x_k) &= h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k)\,\end. #Minimisation operator $\backslash mu\backslash ,$: Given a (k+1)-ary total function $f(y,\; x\_1,\; \backslash ldots,\; x\_k)\backslash ,$: #:$\backslash begin$ \mu(f)(x_1, \ldots, x_k) = z \stackrel\ f(z, x_1, \ldots, x_k)&=0\quad \text\\ f(i, x_1, \ldots, x_k)&>0 \quad \text\ i=0, \ldots, z-1. \end #:Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, the search never terminates. The strong equality operator $\backslash simeq$ can be used to compare partial μ-recursive functions. This is defined for all partial functions ''f'' and ''g'' so that :$f(x\_1,\backslash ldots,x\_k)\; \backslash simeq\; g(x\_1,\backslash ldots,x\_l)$ holds if and only if for any choice of arguments either both functions are defined and their values are equal or both functions are undefined. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Μ-recursive function」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.